package problems.contest;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>https://leetcode.cn/contest/weekly-contest-337/</p>
 *
 * @author habitplus
 * @since 2023/3/20 10:18
 */
public class WCT337 {

    /**
     * T2
     */
    public boolean checkValidGrid(int[][] grid) {
        int n = grid.length;

        if (grid[0][0] != 0) return false;

        int[][] arr = new int[n * n][2];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; j++) {
                arr[grid[i][j]][0] = i;
                arr[grid[i][j]][1] = j;
            }
        }

        int x = 0, y = 0;
        for (int i = 1; i < n * n; ++i) {
            int nx = arr[i][0];
            int ny = arr[i][1];

            if ((Math.abs(nx - x) == 2 && Math.abs(ny - y) == 1)
                    || (Math.abs(ny - y) == 2 && Math.abs(nx - x) == 1)) {
                x = nx;
                y = ny;
            } else {
                return false;
            }
        }

        return true;
    }

    /**
     * T4
     */
    public int findSmallestInteger(int[] nums, int value) {
        int n = nums.length;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int mod;
            if (nums[i] < 0) {
                mod = nums[i] % value + value;
            } else {
                mod = nums[i] % value;
            }
            cnt.put(mod, cnt.getOrDefault(mod, 0) + 1);
        }

        int ret = 0;

        for (int i = 0; i < n; ++i) {
            int mod = ret % value;
            int c = cnt.getOrDefault(mod, 0);
            if (c < 1) {
                break;
            }
            cnt.put(mod, c - 1);
            ++ret;
        }

        return ret;
    }
}
